# 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“
# 房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 
# 
#  计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 
# 
#  示例 1: 
# 
#  输入: [3,2,3,null,3,null,1]
# 
#      3
#     / \
#    2   3
#     \   \ 
#      3   1
# 
# 输出: 7 
# 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 
# 
#  示例 2: 
# 
#  输入: [3,4,5,1,3,null,1]
# 
#      3
#     / \
#    4   5
#   / \   \ 
#  1   3   1
# 
# 输出: 9
# 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
#  
#  Related Topics 树 深度优先搜索 动态规划 二叉树 
#  👍 993 👎 0


from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        f = {}
        g = {}

        def dfs(node: TreeNode):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            f[node] = node.val + g.get(node.left, 0) + g.get(node.right, 0)
            g[node] = max(f.get(node.left, 0), g.get(node.left, 0)) + max(f.get(node.right, 0), g.get(node.right, 0))

        dfs(root)
        return max(f[root], g[root])


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 动态规划
# 选择一个节点, 则不选左右子节点, f(r) = g(l) + g(r)
# 不选一个节点, 则左右节点都可以选择或不选, 取大的值 g(r) = max(f(l), g(l)) + max(f(r), g(r))
# 深度优先遍历, map储存节点与f(r), g(r)
#     def rob(self, root: TreeNode) -> int:
#         f = dict()
#         g = dict()
#
#         def dfs(node: TreeNode):
#             if node is None:
#                 return
#             dfs(node.left)
#             dfs(node.right)
#             f[node] = node.val + g.get(node.left, 0) + g.get(node.right, 0)
#             g[node] = max(f.get(node.left, 0), g.get(node.left, 0)) + max(f.get(node.right, 0), g.get(node.right, 0))
#         dfs(root)
#         return max(f.get(root, 0), g.get(root, 0))
# 稍微优化: 不用map
# [] 第一位储存选择值, 第二位储存不选择值, 递归时直接返回

    # def rob(self, root: TreeNode) -> int:
    #     def dfs(node: TreeNode) -> List[int]:
    #         if node is None:
    #             return [0, 0]
    #         l = dfs(node.left)
    #         r = dfs(node.right)
    #         select = node.val + l[1] + r[1]
    #         no_select = max(l[0], l[1]) + max(r[0], r[1])
    #         return [select, no_select]
    #     f = dfs(root)
    #     return max(f[0], f[1])

if __name__ == '__main__':
    s = Solution()
    #      3
    #     / \
    #    2   3
    #     \   \
    #      3   1
    t1 = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
    r1 = s.rob(t1)
    e1 = 7
    assert r1 == e1, r1
    # 3
#     / \
#    4   5
#   / \   \
#  1   3   1
    t2 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(3)), TreeNode(5, None, TreeNode(1)))
    r2 = s.rob(t2)
    e2 = 9
    assert r2 == e2, r2
